#include "Set1.h"
#include "ExtraAlg.h"


#define PROBLEM_ID 17



void printVector(vector<int> data)
{
	for(std::vector<int>::iterator it = data.begin(); it != data.end(); ++it)
		std::cout << ' ' << *it;
	std::cout << endl;
}

void printArray(int *arr, int size)
{
	for(int i = 0; i < size; i++)
	{
		cout << "  " << arr[i];
	}
	cout << endl;
}

int main(void)
{
	switch(PROBLEM_ID)
	{
	case 11:
		{
			int arr[] = { 1, 2, 4, 6, 8, 10};
			int result = RecursiveBinarySearch(arr, 0, 5, 10);
			std::cout << "Recursive Binary Search : " << result << endl;

			result = IterativeBinarySearch(arr, 0, 5, 10);
			std::cout << "Iterative Binary Search : " << result << endl;

			int data[] = {1, 2, 4, 5, 6, 8}; //6
			vector<int> vec(data, data + sizeof(data)/ sizeof(data[0]));

			int start = 0;
			int finish = 5;
			int m = 2;
			int *missing = new int[m];
			memset(missing, 0, m);
			findMissingNumbersBetweenTwoIndexes(data, start, finish, m, missing);
			printArray(missing, m);
			delete[] missing;

			break;
		}
	case 12: 
		{ 
			int *arrJumps = new int[NUMBER_ELEMENTS];
			int test[NUMBER_ELEMENTS] = { 4, 11, 1, 1, 1, 1, 1, 1, 1, 1}; //10
			for( int i = 0; i < NUMBER_ELEMENTS; i++)
			{
				*(arrJumps + i ) = test[i];
			}

			bool flag = possibleReachLastElement(arrJumps, NUMBER_ELEMENTS);
			cout << "Can we reach the last element? " << flag << endl;

			//void * memset ( void * ptr, int value, size_t num );
			// num - Number of bytes to be set to the value.
            //         size_t is an unsigned integral type.

			// sizeof operator - returns size in bytes of the object representation of the type, that would be returned by expression, if evaluated.

			int *minJumpsToEnd = new int[NUMBER_ELEMENTS];
			memset(minJumpsToEnd, 0, NUMBER_ELEMENTS  * sizeof (*minJumpsToEnd));  // !!!! this is how you initialize a pointer array 

			int testArray[NUMBER_ELEMENTS];
			memset(testArray, 0, sizeof (testArray)); 

			//printArray(minJumpsToEnd, NUMBER_ELEMENTS);
			//printArray(testArray, NUMBER_ELEMENTS);

			int sizeJumps = 0;
			findMinimumJumpsToEnd(arrJumps, NUMBER_ELEMENTS, minJumpsToEnd, &sizeJumps);
			printArray(minJumpsToEnd, sizeJumps + 1);  //sizeJumps stores the index of the last element, not the # of elem which is sizeJumps + 1
			delete[] arrJumps;
			break;
		 }
	case 13: 
		{
			int *arr = new int [NUMBER_ELEMENTS];
			int test[NUMBER_ELEMENTS] =  { 4, 0, 1, 2, 0, 3, 7, 1, 5, 0 };
			for( int i = 0; i < NUMBER_ELEMENTS; i++)
			{
				*(arr + i ) = test[i];
			}
			printArray(arr, NUMBER_ELEMENTS);
			moveNonZeroToLeft(arr, NUMBER_ELEMENTS);
			printArray(arr, NUMBER_ELEMENTS);
			delete[] arr;
			break;
		}
	case 14: 
		{
			string words[] = {"cab", "aaa"};
			printOrder(words, 2, 3);
			break;
		}
	case 15: 
		{
			string result = pattern ( 5 );	
			string result2 = lookAndSaySequence( 5 );
			cout << result << endl;
			cout << result2 << endl;
			break;
		}
	case 16: 
		{
			//perfectSquares( 25 );
			int *arr = new int [NUMBER_ELEMENTS];
			int test[NUMBER_ELEMENTS] =  { 4, 0, 1, 2, 0, 3, 7, 1, 5, 0 };
			for( int i = 0; i < NUMBER_ELEMENTS; i++)
			{
				*(arr + i ) = test[i];
			}
			//twoSumVersion1(arr, NUMBER_ELEMENTS, 7);
			//twoSumVersion2(arr, NUMBER_ELEMENTS, 7);
			//threeSumVersion(arr, NUMBER_ELEMENTS, 7);

			
			if( subSetSumProblem(arr, NUMBER_ELEMENTS, 7))
			{
				cout << "Yes " << endl;
			}
			else
			{
				cout << "No" << endl;
			}

			//knapSack( W,  wt,  val,  n);
			break;
		}
	case 17: 
		{
			string s = " A man, a plan, a canal  -- Panama! ";
			if( isPalindrome( s ) )
			{
				cout << "Yes - Palindrome" << endl;
			}

			break;
		}
	case 18: 
		{
			break;
		}
	default:
		{
			cout << "The problem ID is not defined" << endl;
			break;
		}
	}

	getchar();
	return 0;
}